class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def parseTree(preorder, pbeg, pend, inorder, ibeg, iend):
    if pend-pbeg == 0:
        return None

    rootval = preorder[pbeg]
    leftlen = inorder.index(rootval, ibeg, iend)-ibeg
    rightlen = iend-ibeg-1-leftlen
    root = TreeNode(rootval)
    root.left = parseTree(preorder, pbeg+1, pbeg+leftlen+1, inorder, ibeg, ibeg+leftlen)
    root.right = parseTree(preorder, pbeg+1+leftlen, pend, inorder, ibeg+1+leftlen, iend)
    return root

class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: []
        :type inorder: []
        """
        if not preorder or len(preorder) != len(inorder):
            return None

        return parseTree(preorder, 0, len(preorder), inorder, 0, len(inorder))

if __name__ == '__main__':
    print Solution().buildTree(['A', 'B', 'D', 'E', 'C', 'F'], ['D', 'B', 'E', 'A', 'F', 'C'])
    pass

